In order to clarify the following explanation, the situation of transactions of the type known as "electronic wallet" will be used. This technology was the subject of a special issue (No. 158) of the magazine "L'Echo des Recherches" published in the 4th quarter of 1994. Of particular interest is an article by Marc Girault and Luc Vallee entitled "Signature electronique et application au paiement electronique" (Electronic Signatures and their Application to Electronic Payment).
Although electronic wallet technology has developed considerably over recent years, the security of this type of application still poses problems into which research is continuing. Various solutions to these problems are possible and may be examined on a security/cost basis.
In this type of system an electronic wallet (EW) card carries a balance, i.e. a certain quantity of values (currency, tokens, consumption units, etc.). On payment of a sum m, this balance is reduced by m units, the card producing proof that m units have been debited; this constitutes the guarantee of payment for a trader equipped with a terminal or server on which the user performs the transaction. This proof is the condition on which the trader receives payment in normal currency from the authority who issued the electronic wallet; this authority may be referred to as the "bank".
The proof must be verified to avoid the use of forged cards: it should not be possible to construct out of nothing i.e. without a card, proof capable of being accepted as authentic. The proof should also prevent manipulations such as converting a sum m into a sum m' that is greater than m, or reusing the same proof to pay the sum due to a trader twice or, again, paying sums not due to other traders.
In the following description the various participants in these systems will be described as the "user", "service provider" and "bank". The user has an EW card to pay a service provide while the bank is the body issuing the cards.
The techniques in current use may be broken down into three broad categories according to whether the signatures they use have a secret key, a public key or interactive keys.
In the first type, a terminal may be disconnected from the bank (said to be offline) or connected directly to the bank. The first configuration (offline) is the commonest in the various existing electronic wallet systems. It consists in calculating the proof z using a secret key algorithm f applied to parameter i representing the number of the EW card, and to parameter M which stands for all the following parameters:
m: the sum of the transaction, PA1 j: the number of the security module, usually known as the Secure Application Module or SAM, PA1 r: a random value or, more simply, the reading on a counter. PA1 security is based on the impossibility of reading the master key KM in the SAM and thus on the physical security of the SAMs; since the SAMs are installed in every terminal they are very widespread. This security is therefore difficult to preserve. Possession of the master key KM would make large-scale fraud possible: cards could be produced having any identity i that no blacklist system would be capable of intercepting; PA1 the SAMs are located in the terminals or on the service provider's premises. This creates practical problems when several types of EW card, each having its own SAM, are to be accepted. This is the case which, incidentally, is very widespread in practice, where more than one bank issues its own EW cards. PA1 the cost of cards capable of performing calculations based on RSA-type public-key algorithms is high since the computing power required for a given response time is significant; PA1 a large amount of data must be stored in and collected from the terminal; M and y must be stored for each transaction. Given the current length of public keys (512 bits), this set of data amounts to something of the order of 1.5 kbits. PA1 the cost of cards capable of performing calculations based on public-key algorithms is high since the computing power required for a given response time is significant; PA1 a SAM is required. PA1 g: 64 to 512 bit expansion function, PA1 h: hashing function yielding a 64-bit result, PA1 *: operation restricting to 128 low order bits, PA1 S.sub.A and P.sub.A : the authority's secret and public keys: 768 bits, PA1 i: identity of the card: 64 bits, PA1 n: module: 512 bits, PA1 cer: S.sub.A (i,n,e): 768 bits, PA1 e: n first number: 16 bits, PA1 v: 1/I.sup.1/e mod n: 512 bits. PA1 1) the terminal sets the sum m of the transaction, draws a random number r and constitutes the parameter M, combining m, j and r; it then transmits M to the card; PA1 2) the card checks that the balance is greater than the sum m of the transaction; if this is the case, the card draws a random number x, calculates t=x.sup.e mod n and b=h(t*,M) and transmits i, b and certificate cer=S.sub.A (i,n,e) to the terminal; PA1 3) the terminal checks the certificate and obtains i, n and e, selects a random number c less than e and sends c to the card; PA1 4) the card calculates y=xv.sup.c mod n, reduces the balance by m and transmits y and t* to the terminal; PA1 5) the terminal calculates I=g(i), the quantity u=(y.sup.e I.sup.c mod n)*, followed by h(u,M) and checks that b is equal to h(u,M); the terminal then increases the balance by m. PA1 the card selects a random number x, calculates t=x.sup.e mod n and sends b=h(M,t) to the terminal, PA1 the terminal selects a random number c such that 0&lt;c&lt;e and sends it to the card, PA1 the card responds with y=xv.sup.c mod n, PA1 the terminal then checks that if u=y.sup.e I.sup.c, then b=h(M,u) since v.sup.e I=1 mod n. PA1 the terminal transmits a parameter comprising at least the sum of the transaction to the card, PA1 the card debits the said sum from the balance, PA1 the card and the terminal calculate and exchange various data, certain of which are signed by the card by means of a public or secret algorithm, PA1 the terminal checks the data signed by the said public or secret algorithm and stores the individual parameters of the various transactions effected, PA1 the centralized system periodically collects the stored data when it is connected to the terminal and credits the service provider with the corresponding amounts, PA1 said procedure being characterized by the fact that it is a dual signature procedure, the data being signed by the card by means of the public or secret algorithm comprising a proof z that the card has been debited, said proof z being a function of the parameter and of a secret debit key, the terminal thereby also storing the different proofs of the transactions effected without being able to check said proofs, the centralized system also collecting said proofs and checking them using the secret debit key and only crediting the service provider on condition the checking operation is positive.
This gives z=f(k,m,j,r) where k is the secret key of the EW card whose identity is i. This key is dependent on i due to a mechanism of diversifying the keys according to the number i of the card. The SAM is a chip card located in the terminal whose physical properties enable it to act as a secure, protected cash register. The SAM therefore checks the certificate z and accumulates the sums received. It is regularly emptied so that the service provider's profits are credited by the bank; this is done using a secure procedure between the SAM and the bank. There are no particular difficulties involved in this procedure, so it will not be described here.
In order to check certificate z the SAM needs to know the keys of all EW cards. In practice this is done by calculating the keys k of the EW cards using the diversification formula k=g (KM,i), where KM is a master key that is valid for the entire system and present in all SAMs.
This method is shown in FIG. 1 attached where the user's EW card is numbered 10, the service provider's terminal is numbered 20 and its SAM 25, and the bank is numbered 30. The arrow running from terminal 20 towards card 10 represents the transmission of parameters n to the card and the arrow running in the opposite direction represents the transmission of the certificate z to the terminal.
This first method has the advantage of using low-cost cards. However, it has the following drawbacks:
Turning now to configurations in which the service provider terminal is connected to the bank (i.e. online), the SAMs are no longer inside the terminals and the certificate must be checked at the bank. This procedure is illustrated in FIG. 2 attached in which the numbering is the same as in FIG. 1.
In practice this system is of little interest since the telecommunications costs are prohibitive. Electronic wallet systems must be cost-effective even for transactions involving very small sums.
Systems that incorporate a signature procedure using a public key algorithm may be divided into two types depending on whether or not they use a Secure Application Module (SAM).
If no SAM is to be used, the certificate z of the foregoing secret-key systems is replaced by a signature based on a public key algorithm such as the RSA (Rivest-Shamir-Adleman) algorithm. Each card has a pair of secret and public keys, s and p respectively, and the proof of debit defined by parameter M is obtained by calculating a signature y=s(M).
The service provider can check this signature using the public key. All the signatures can be stored for periodic collection to record payments by the bank. In this type of configuration the public key p must also be authenticated by the card-issuing authority since the mere holding of a pair of secret and public keys, s and p does not prove that the EW card is genuine; this type of pair can easily be detected, for example using a personal computer on which appropriate software has been installed. The EW card must therefore provide the terminal not only with its public key p but also a certificate linked to public key p. This certificate will be referred to as "cer" below. The certificate "cer" is checked with the bank's public key PA.
FIG. 3 attached illustrates this configuration. Although the numbering is the same as for FIGS. 1 and 2, it will be noted that the service provider's terminal 20 is provided with means 26 of collecting or recording card numbers i, parameters M, certificates cer and signatures y.
The advantage of this system is that no SAM or secret master key is present in the terminals with the risks that this involves. This system is therefore more secure and has greater flexibility.
However, the system has the following drawbacks:
In the version with a Secure Application Module, transactions are accumulated in the terminal for subsequent collection by the bank. Since the accumulation operation presents security risks, given that any attempted fraud would involve attempting to modify the sum accumulated by the service provider, a SAM is required to check transaction signatures and accumulate them.
FIG. 4 attached illustrates this version using the same numbering as the previous figures.
The advantage of this version is that the terminal contains no secret master key, thereby improving security. There are, however, two drawbacks remaining:
The third type of procedure uses interactive signature systems. The use of this technique makes it possible to reduce considerably the computing power required by the cards by a ratio of 10 to 20 with the parameter settings currently in use. For identical computing power, the response times are thus better. For identical response times, the cost of components for EW cards is less.
Generally speaking, two authentication systems are used, namely the Guillou-Quisquater (GQ) and the Fiat-Shamir (FS). The issue of "L'Echo des Recherches" cited above includes all the bibliographic references concerning these two systems.
We will give a brief summary of this type of signature procedure, using the CQ system as an example. In this example the card, referred to as Ci, uses the following functions or parameters:
Secure terminal Tj posses public key P.sub.A, g, h and is identified by j in 64 bits.
The procedure is as follows:
This procedure can be summarized as follows:
This procedure is illustrated in FIG. 5 attached. Its advantage lies in the fact that the computing power required is less than in RSA-type procedures. But one drawback remains: the procedure requires a SAM. The interactive signature is of no value unless it is certain that random number c has been correctly submitted to the card in the given order. For this reason interactive signatures are known as "throw-away"; they can only be used at the time they are obtained. The interactive signature comprises data M, cer, b, c, and y. It is therefore easy to create this data out of nothing: if cer and M are known, p and i can be obtained; all that remains is to select y and c and to calculate t=y.sup.e I.sup.c and b=h(M,t). The data obtained M, cer, b, c and y constitute a valid signature.
The purpose of the present invention is to overcome precisely these drawbacks.